package leetcode4;

public class Day14 {
    public int numSquares(int n) {
        int x = (int)Math.sqrt(n), max = 0x3f3f3f3f;
        int[][] dp = new int[x+1][n+1];
        //从前i个数中选（要求每个数都是完全平方数,每个数取上平分），和为j，使用到的的最少数字-数量
        //这个数选/不选,min()
        for(int i = 1; i < n+1; i++) dp[0][i] = max;
        for(int i = 1;i < x + 1; i++) {
            for(int j = 0;j < n + 1; j++) {
                dp[i][j] = dp[i-1][j];
                if(j >= i * i) {
                    dp[i][j] = Math.min(dp[i][j],dp[i-1][j - i*i]+1);
                }
            }
        }
        return dp[x][n];
    }
}
